package arithmetic.jd;

import java.util.*;


/**
 * 京东笔试题： 2.如果"X"和“Y”是合法的库列那么“XY”也是一合法的括号库列 3.如果"X"合法的库列那么"(X)"也合法的括号库列 4. 每个合法的括号序列都可以甶上面的规则生成. 例如 "","()","()()()"都是合法的。现在有个合法的括号序列s，一次移除操作为两步： 1. 移除库列s中的第一个左括号 2. 移除库列s中任意 一个右括号. 保证操作后之后s还是一个合法的括好序列。
 *
 * 现在想知道使用上述的移除操作有多少种方案可以把序列s 变为空。
 *
 * 如果两个方案中有一次移除操作的移除的是不同的右括号就认为是不同的方案。
 *
 * 例如 s="()()()()"，输出为1，因为每次都只能选择被移除的左括号所相邻的右括号. s="(((())))",输出为24，第一次有4种情况，第二次有3中情况，..一次类推 4*3*2*1 =24
 *
 * 输入描述：
 *
 * 输入包括一行，一个合法的括号序列s，序列长度 length (2<=lenth<=20). 输出，方案个数
 */
public class Jd {

    public static void main(String[] args) {
        //	Scanner sc = new Scanner(System.in);
        //	String n = sc.next();
        // 40,41
        String s = "()()()";
        System.out.println(cal(s));

    }

    public static int cal(String string) {
        int count = 0;
        char[] chars = string.toCharArray();
        if (chars[0] == ')') {
            return count;
        }
        List<Integer> list = countRight(chars);
        for (int i : list) {
            //切割括号后,substring 含头不含尾
            String newString = string.substring(1, i) + string.substring(i + 1, string.length());
            if (validate(newString.toCharArray())) {
                // 只有两对以上括号才有计算价值，要不然就重复计算了
                if (newString.length() > 3) {
                    count += cal(newString);
                } else {
                    count++;
                }
            }
        }
        return count;
    }

    // 算出右括号的位置，用List数组来记录右括号出现的位置。 方便切割。
    public static List<Integer> countRight(char[] chars) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ')') {
                list.add(i);
            }
        }
        return list;
    }

    public static boolean validate(char[] a) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < a.length; i++) {
            char c = a[i];
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.empty()) {
                    return false;
                }
                stack.pop();
            }
        }
        return true;
    }
}
